import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
import java.lang.Math;

abstract public class GraphSearch {
	
	protected HashMap<Noeud, Integer> open;
	protected HashMap<Noeud, Integer> close;
	protected HashMap<Noeud, HashMap<Noeud, Integer>> successeurs;
	protected HashMap<Noeud, Noeud> tablePointeurs;
	protected HashMap<Noeud, Integer> heuristique;
	protected Noeud noeudFin;
	protected int nombreEtapes;

	public GraphSearch(HashMap<Noeud, HashMap<Noeud,Integer>> s){
		open = new HashMap<Noeud, Integer>();
		close = new HashMap<Noeud, Integer>();
		tablePointeurs = new HashMap<Noeud, Noeud>();
		nombreEtapes = 0;
		if(s!=null){
			successeurs = s;
		}else{
			successeurs = new HashMap<Noeud, HashMap<Noeud, Integer>>();
		}
		
	}
	
	public Integer algo(Noeud debut, ArrayList<Noeud> fin){
		
		// Initialisation
		open.put(debut, 0);
		

		noeudFin = fin.get(0); 
		
		// BOUCLE
		while(!open.isEmpty()){
			nombreEtapes++;
			// Choisir un noeud n dans OPEN
			Noeud n = choisir(open);
			int value = open.get(n);
			System.out.println("On a choisi "+ n.getNom());			
			
			// Enlever n de OPEN et le mettre dans CLOSE
			close.put(n, open.get(n));
			open.remove(n);
			
			// Si n est dans N
			if(contientFin(fin,n)){
				noeudFin = n;
				System.out.println("--------> REUSSITE");
				System.out.println("***** Nombre d'etapes necessaire : " + nombreEtapes);
				return 0;				
			}
			
			
			
			// Pour chaque éléments p de succ(n)
			for(Entry<Noeud, Integer> entry : succ(n).entrySet()){
				Noeud p = entry.getKey();
				int cout_succ = successeurs.get(n).get(p);
				
				// Si p n'est ni dans OPEN ni dans CLOSE
				if(!contientNoeud(open, p) && !contientNoeud(close, p)){
				//if(!open.containsKey(p) && !close.containsKey(p)){
					// Etablir un pointeur entre p et n					
					tablePointeurs.put(p, n);
					mettreDansOpen(p,(cout_succ + value));
				}
				
				// Si p est dans OPEN
				else if(contientNoeud(open,p)){
				//else if(open.containsKey(p)){
					// Decision de la redirection
					int decider_val = value + cout_succ;
					if(decider(p,decider_val)){
						// Redirection du pointeur entre p et n
						maj_open(p,decider_val);
						tablePointeurs.put(p, n);			
					}
					
				}
				
				// Si p est dans CLOSE
				else if(contientNoeud(close,p)){
				//else if(close.containsKey(p)){
					// Decision de la redirection
					int decider_val = value + cout_succ;
					if(decider(p,decider_val)){
						// Redirection du pointeur entre p et n
						tablePointeurs.put(p, n);
						
						// Enlever p de CLOSE et mettre p dans OPEN
						Noeud temp = trouverNoeud(close,p);
						mettreDansOpen(temp,close.get(temp));
						close.remove(temp);
					}
				}
			}
			System.out.print("OPEN : ");
			afficher(open);
			System.out.print("CLOSE : ");
			afficher(close);
			saut_ligne();
		}
		System.out.println("Fin de l'algorithme");
		return -1;		
		
	}

	public void mettreDansOpen(Noeud p, int i) {
		// TODO Auto-generated method stub
		
	}

	private void maj_open(Noeud p, int deciderVal) {
		// TODO Auto-generated method stub
		open.remove(p);
		open.put(p, deciderVal);
	}

	private void saut_ligne() {
		// TODO Auto-generated method stub
		System.out.println();
		
	}
	

	protected boolean decider(Noeud p, int val){
		//trouver la valeur avec le prédecesseur
		int valeur = 0;
		if(contientNoeud(open,p)){
			Noeud n = trouverNoeud(open,p);
			valeur = open.get(n);
		}else{
			Noeud n = trouverNoeud(close,p);
			valeur = close.get(n);
		}
		
		return val<valeur;
		
	}

	protected Noeud choisir(HashMap<Noeud, Integer> o){
		Integer min = null;
		Noeud retour = null;
		
		for(Entry<Noeud, Integer> entry : o.entrySet()){
			Noeud p = entry.getKey();
			Integer v = entry.getValue();
			
			if(min == null || v < min){
				retour = p;
				min = v;
			}
		}
		
		return retour;
	}
	
	private HashMap<Noeud, Integer> succ(Noeud n){
		int[] succ_courant = n.getSequence();
		if(succ_courant != null){
			int[][] succ = construireSuccesseur(succ_courant);
			HashMap<Noeud, Integer> retour = new HashMap<Noeud, Integer>();
	
			for(int i = 0 ; i < succ.length; i++){
				if(!egal(succ_courant,succ[i])){
					NoeudTaquin noeud = new NoeudTaquin("",succ[i]);
					noeud.construireNom();
					retour.put(noeud, 1);
				}
			}
			
			//On met a jour les successeurs
			successeurs.put(n, retour);
		}

		return successeurs.get(n);
	}
	
	
	private boolean egal(int[] succCourant, int[] is) {
		// TODO Auto-generated method stub
		if(succCourant.length == is.length){
			
			int i=0;
			while(i<succCourant.length && succCourant[i] == is[i]){
				i++;
			}
			return i==succCourant.length;
			
		}else{
			
			return false;
			
		}
	}

	public ArrayList<Noeud> resultat(){
		ArrayList<Noeud>retour = new ArrayList<Noeud>();
		Noeud noeudCourant = noeudFin;
		retour.add(noeudCourant);
		while(tablePointeurs.get(noeudCourant) != null)
		{
			retour.add(tablePointeurs.get(noeudCourant));
			noeudCourant = tablePointeurs.get(noeudCourant);
		}
		Collections.reverse(retour);
		return retour;
	}
	
	protected void afficher(HashMap<Noeud, Integer> o){
		
		for(Entry<Noeud, Integer> entry : o.entrySet()){
			Noeud p = entry.getKey();
			Integer v = entry.getValue();
			System.out.print(p.getNom() +"("+ v + "), ");
		}
		System.out.println();
	}
	
	public int[][] construireSuccesseur(int[] seq){
		
		int dimension = Application.getInstance().getDimension();
		int[][] newSequences = new int[4][dimension*dimension] ;
		for(int i =0; i<4; i++){
			//newSequences[i] = seq;
			for(int k=0; k<seq.length; k++){
				newSequences[i][k] = seq[k];
			}
		}
		
		int i=0;
		while(i < seq.length && seq[i] != seq.length){
			i++;
		}
		int posTrou = i;
		
		int newPosTrou;
		
		newPosTrou = dimension + posTrou;
		newSequences[0] = permuter(newSequences[0], newPosTrou, posTrou);
		
		newPosTrou = Math.abs(posTrou - dimension);
		newSequences[1] = permuter(newSequences[1], newPosTrou, posTrou);
		
		newPosTrou = posTrou - 1;
		newSequences[2] = permuter(newSequences[2], newPosTrou, posTrou);
		
		newPosTrou = posTrou + 1;
		newSequences[3] = permuter(newSequences[3], newPosTrou, posTrou);

		return newSequences;
		
	}
	
	public int[] permuter(int[] seq,int a, int b){
		int temp;
		int[] resultat;
		
		resultat = seq;
		if(a < seq.length && valide(a,b)){
			temp = resultat[a];
			resultat[a] = resultat[b];
			resultat[b] = temp;
		}
			
		return resultat;
	}
	
	private boolean valide(Integer id1, int id2) {
		int dimension = Application.getInstance().getDimension();
		if( id1+dimension == id2 || id1-dimension == id2 || (id1+1 == id2 && id2%dimension!=0) || (id1-1 == id2 && id2%dimension!=1)){
			return true;
		}
		else{
			return false;
		}
	}

	private boolean contientNoeud(HashMap<Noeud, Integer> hash, Noeud n){
		boolean bool = false;
		int[] seq = n.getSequence();
		
		if(seq == null){
			
			bool = false;
			
		}else{
			
			for(Entry<Noeud, Integer> entry : hash.entrySet()){
				int[] temp = entry.getKey().getSequence();
				if(egal(temp,seq)){
					bool = true;
				}
			}
			
		}
		return bool;
	}
	
	private Noeud trouverNoeud(HashMap<Noeud, Integer> hash, Noeud p){
		Noeud n = null;
		if(hash.containsKey(p)){
			n = p;
		}else{
					
			int[] seq = p.getSequence();
			for(Entry<Noeud, Integer> entry : hash.entrySet()){
				int[] temp = entry.getKey().getSequence();
				if(egal(temp,seq)){
					n = entry.getKey();
				}
			}
			
		}
		
		return n;
	}
	
	private boolean contientFin(ArrayList<Noeud> fin,Noeud p){
		boolean resultat = false;
		int[] seq = p.getSequence();
		
		if(seq == null){
			resultat = fin.contains(p);
		}else{
			int i=0;
			while(i<fin.size() && !egal(seq,fin.get(i).getSequence())){
				i++;
			}
			resultat = (i!=fin.size());
		}
		
		return resultat;
	}
}
